package interview.questions.数组排序汇总;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Date;

/**
 * 数组排序方法
 */
public class Algorithm {
    private static Logger logger = LoggerFactory.getLogger(Algorithm.class);

    /**
     * 冒泡
     */
    public static void bubbleSortAsc(int[] a) {
        logger.debug("冒泡排序开始");
        Long Before = new Date().getTime();
        int n = a.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = n - 1; j > i; j--) {
                if (a[j - 1] > a[j]) {
                    int temp = a[j - 1];
                    a[j - 1] = a[j];
                    a[j] = temp;
                }
            }
        }
        Long After = new Date().getTime();
        logger.debug("冒泡排序花费时间={}",After-Before);
    }
    /**
     * 冒泡-降序
     */
    public static void bubbleSortDes(int[] a) {
        int n = a.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = n - 1; j > i; j--) {
                if (a[j - 1] < a[j]) {
                    int temp = a[j - 1];
                    a[j - 1] = a[j];
                    a[j] = temp;
                }
            }
        }
    }

    /**
     * 堆排序
     */
    public static void heapSortAsc(int[] a) {
        int i;
        int n = a.length;
        for (i = n / 2 - 1; i >= 0; i--) {  // 从最后一个非终端节点开始，逐个向上遍历
            maxHeapDown(a, i, n - 1);
        }
        for (i = n - 1; i > 0; i--) {
            int tmp = a[0];
            a[0] = a[i];
            a[i] = tmp;
            maxHeapDown(a, 0, i - 1);
        }
    }

    private static void maxHeapDown(int[] a, int start, int end) {
        int father = start;
        int child = 2 * father + 1; // 左孩子
        while (child <= end) {
            if (child < end && a[child] < a[child + 1]) {
                child++;  // 如果右孩子大，将左孩子变为右孩子
            }
            if (a[father] >= a[child]) {
                break;
            } else {
                int tmp = a[father];
                a[father] = a[child];
                a[child] = tmp;
            }
            father = child;
            child = 2 * father + 1;
        }
    }


    /**
     * 插入排序
     */
    public static int[] sortAsc(int[] ins) {

        for (int i = 1; i < ins.length; i++) {
            for (int j = i; j > 0; j--) {
                if (ins[j] < ins[j - 1]) {
                    int temp = ins[j - 1];
                    ins[j - 1] = ins[j];
                    ins[j] = temp;
                }
            }
        }
        return ins;
    }

    /**
     * 归并排序
     */
    public static void mergeSortAsc(int[] a, int start, int end) {
        if (start < end) {
            int median = (start + end) / 2;
            mergeSortAsc(a, start, median);
            mergeSortAsc(a, median + 1, end);
            merge(a, start, median, end);
        }
    }

    private static void merge(int[] a, int start, int median, int end) {
        int i;
        int j;
        int k;
        int n1 = median - start + 1;
        int n2 = end - median;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (i = 0, k = start; i < n1; i++, k++) {
            L[i] = a[k];
        }
        for (i = 0, k = median + 1; i < n2; i++, k++) {
            R[i] = a[k];
        }
        for (k = start, i = 0, j = 0; i < n1 && j < n2; k++) {
            if (L[i] < R[j]) {
                a[k] = L[i];
                i++;
            } else {
                a[k] = R[j];
                j++;
            }
        }
        while (i < n1) {
            a[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            a[k] = R[j];
            j++;
            k++;
        }
    }

    /**
     * 快速排序
     */
    public static void quickSortAsc(int[] a, int low, int high) {
        if (low >= high) {
            return;
        }
        int i = low;
        int j = high;
        int temp = a[i];
        while (i < j) {
            while (i < j && a[j] >= temp) {
                j--;
            }
            if (i < j) {
                a[i++] = a[j];
            }
            while (i < j && a[i] < temp) {
                i++;
            }
            if (i < j) {
                a[j--] = a[i];
            }
        }
        a[i] = temp;
        quickSortAsc(a, low, i - 1);
        quickSortAsc(a, i + 1, high);
    }

    /**
     * 基数排序
     */
    public static void radixSortAsc(int[] a) {
        int max = getMax(a);
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countSort(a, exp);
        }
    }

    private static int getMax(int[] a) {
        int max = a[0];
        for (int i : a) {
            if (i > max) {
                max = i;
            }
        }
        return max;
    }

    private static void countSort(int[] a, int exp) {
        int[] output = new int[a.length];
        int[] buckets = new int[10];
        for (int anA : a) {
            buckets[(anA / exp) % 10]++;
        }

        for (int i = 1; i < 10; i++) {
            buckets[i] += buckets[i - 1];
        }

        for (int i = a.length - 1; i >= 0; i--) {
            output[buckets[(a[i] / exp) % 10] - 1] = a[i];
            buckets[(a[i] / exp) % 10]--;
        }
        for (int i = 0; i < a.length; i++) {
            a[i] = output[i];
        }
        output = null;
        buckets = null;
    }

    /**
     * 选择排序
     */
    public static void sortSelectAsc(int[] a) {
        int i;
        int j;
        int temp = 0;
        int flag = 0;
        for (i = 0; i < a.length; i++) {
            temp = a[i];
            flag = i;
            for (j = i + 1; j < a.length; j++) {
                if (a[j] < temp) {
                    temp = a[j];
                    flag = j;
                }
            }
            if (flag != i) {
                a[flag] = a[i];
                a[i] = temp;
            }
        }
    }

    /**
     * 希尔排序
     */
    public static void shellSortAsc(int[] a) {
        int length = a.length;
        for (int gap = length / 2; gap > 0; gap /= 2) {
            for (int i = 0; i < gap; i++) {
                for (int j = i + gap; j < length; j += gap) {  //每个子序列都从第二个开始
                    if (a[j] < a[j - gap]) {
                        int temp = a[j];
                        int k = j;
                        while (k >= gap && a[k - gap] > temp) {
                            a[k] = a[k - gap];
                            k -= gap;
                        }
                        a[k] = temp;
                    }
                }
            }
        }
    }
}
